package lanQiaoBei.搜索与图论.最短路.floyd;
import java.io.*;
import java.math.*;
import java.util.*;
/*floyd求多源最短路
*题目描述
定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路。

输入格式
第一行包含三个整数n，m，k

接下来m行，每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。

接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。

输出格式
共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过10000。

样例
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
* */
public class P1 {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    final static int N=210;
    static int d[][]=new int[N][N],n,m,Q;

    static void scan()throws Exception{
           String[]ss=br.readLine().split(" ");
           n=Integer.parseInt(ss[0]);m=Integer.parseInt(ss[1]);Q=Integer.parseInt(ss[2]);
           for(int i=1;i<=n;i++)
               Arrays.fill(d[i],0x3f3f3f3f);
           while(m-->0){
                ss=br.readLine().split(" ");
                int a=Integer.parseInt(ss[0]),b=Integer.parseInt(ss[1]),c=Integer.parseInt(ss[2]);
                d[a][b]=Math.min(d[a][b],c);
           }
    }
    static void floyd(){
           for(int k=1;k<=n;k++)
               for(int i=1;i<=n;i++)
                   for(int j=1;j<=n;j++)
                   d[i][j]=Math.min(d[i][j],d[i][k]+d[k][j]);
    }
    public static void main(String[]args)throws Exception{
           scan();
           floyd();
           while(Q-->0) {
               String[] ss = br.readLine().split(" ");
               int x = Integer.parseInt(ss[0]), y = Integer.parseInt(ss[1]);
               if (d[x][y] > 0x3f3f3f3f / 2) System.out.print("impossible");
               else System.out.print(d[x][y]);
           }
    }
}
